public class Test {
    /*
    题目 1：移动 0
     */
    public static void moveZeroes1(int[] nums) {
        int dest = -1;
        int cur = 0;

        int n = nums.length;

        while(cur < n){
            if(nums[cur] != 0){
                swap(nums, ++dest, cur);
            }
            cur++;

        }
    }

    public static void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main1(String[] args) {
        int[] arr = {1};
        moveZeroes(arr);
        System.out.println(arr);
    }

    public static void moveZeroes(int[] nums) {
        for(int cur = 0, dest = -1; cur < nums.length; cur++){
            if(nums[cur] != 0){
                dest++;
                int temp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = temp;
            }
        }
    }

    /*
    题目 2 ：复写 0：
     */
    // 自己的思路:
    // cur 从左到右遍历，停在需要复写的 0 下标位置
    // end 每次从结尾开始，arr[end] = arr[end - 1]，在 cur 的后一个下标停下
    // 这其实就是暴力求解！🤦‍
    public static void duplicateZeros1(int[] arr) {
        int cur = 0;
        int n = arr.length;

        while(cur < n){
            int end = n - 1;

            while(cur < n && arr[cur] != 0){
                cur++;
            }

            while(cur  < end){
                arr[end] = arr[end - 1];
                end--;
            }

            cur = end + 2;
        }
    }

    public static void duplicateZeros2(int[] arr) {
        int n = arr.length;

        for(int i = 0; i < n; i++){
            if(arr[i] == 0){
                for(int j = n - 1; i < j; j--){
                    arr[j] = arr[j - 1];
                }
                i++;
            }
        }

    }

    public static void main2(String[] args) {
        int[] arr = {1, 0, 2, 3, 0, 4, 5, 0};
        duplicateZeros(arr);
    }

    public static void duplicateZeros(int[] arr) {
        int cur = 0;
        int dest = -1;

        int n = arr.length;

        // cur 指向的值为 非0，dest 走一步
        // cur 指向的值为 0，dest 走两步

        // dest 所能走的总数为 n 或者 n - 1 ！
        // arr = [1,0,2,3,0,4,5,0]
        // 对应的 dest 依次走 1 + 2 + 1 + 1 + 2 + 1 = 8
        // 而 arr = [1,0,2,3,0,4]
        // 对应的 dest 依次走 1 + 2 + 1 + 1 + 2 = 7，dest 的最终下标越界了！

        // 1. 找到复写的最后一个数字的下标
        while(cur < n){
            if(arr[cur] != 0){
                dest += 1;
            }else{
                dest += 2;
            }

            if(dest >= n - 1){
                break;
            }

            cur++;
        }

        // 2. 处理边界条件！
        if(dest == n){
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }

        // 3. 进行复写
        while(cur >= 0){
            if(arr[cur] != 0){
                arr[dest--] = arr[cur--];
            }else{
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }

        }
    }

    /*
    题目 3: 快乐数
     */
    // 借鉴 链表是否存在环 的解题思路
    public int bitSum(int n){
        int sum = 0;

        while(n > 0){
            int t = n % 10;
            sum += t * t;
            n /= 10;
        }

        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = bitSum(n);

        while(slow != fast){
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }

        return fast == 1;
    }

    /*
    题目 4：盛最多水的容器
     */
    // 最初的想法是暴力枚举，但超时了
    // 是否可以通过减少枚举的次数呢？
    // 容积 = H * W (高 × 宽)
    // 1. H 减小，W 减小 一定容积减小
    // 2. H 不变，W 减小，一定容积减小
    // 双指针思路：短的那边，与比他长的算出容积之后，后面可以不需要再枚举了！
    // 因为 固定短的这边，短的为高度，与长的宽度算出一个容积
    // 如果固定短的，从长的那边枚举过来，容积一定会减少的！！
    // 后续遇到更长的，没用，宽度减少！！容积一定减少
    // 后续遇到更短的，高度减少，宽度减少，容积也一定减少！！
    public int maxArea1(int[] h) {
        int left = 0;
        int right = h.length - 1;
        int max = Integer.MIN_VALUE;
        int sum = 0;

        while(left < right){
            if(h[left] < h[right]){
                sum = (right - left) * h[left];
                if(max < sum){
                    max = sum;
                }
                left++;
            }else{
                sum = (right - left) * h[right];
                if(max < sum){
                    max = sum;
                }
                right--;

            }
        }

        return max;
    }

    public int maxArea(int[] h) {
        int left = 0;
        int right = h.length - 1;
        int ret = 0;

        while(left < right){
            int v = Math.min(h[left], h[right]) * (right - left);
            ret = Math.max(ret, v);
            if(h[left] < h[right]) left++;
            else right--;
        }
        return ret;

    }

}
